package subjectlist;


/**
 * 题目描述：回文字符串是指一个字符串从左到右与从右到左遍历得到的序列是相同的。例如，“abcba”就是回文字符串，而“abcab”则不是回文字符串
 */
public class K如何求字符串里的最长回文子串 {


    private static class 动态规划法{

    }


    private static class 中心扩展法{

    }


    /**
     * O(N)
     */
    private static class Manacher{

        private int center;
        private int palindromeLen;
        private int getCenter(){
            return center;
        }
        private int getLen(){
            return palindromeLen;
        }
        int min(int a,int b){
            return a>b?b:a;
        }

        /**
         * 方法功能：找出字符串最长的回文子串
         * 输入参数：str为字符串，center为回文字符的中心字符，len表示回文字符串长度
         * 如果长度为偶数，center表示中间偏左边的那个字符的位置
         */
        public  void manacher(String str){
            //字符串的长度
            int len =str.length();
            int newLen=2*len+1;
            //插入分隔符后的字符串
            char[] s=new char[newLen];
            int []p=new int[newLen];
            int i=0;
            int id=0;
            for (i = 0; i < newLen; i++) {
                //构造填充字符串
                s[i]='*';
                p[i]=0;
            }
            for (i = 0; i < len; i++) {
                s[(i+1)*2]=str.charAt(i);
            }
            center=-1;
            palindromeLen=-1;
            for (i = 1; i < newLen; ++i) {
                if(id+p[id]>1){
                    p[i]=min(id+p[id]-i,p[2*id-i]);
                }else {
                    p[i]=1;
                }
                //然后接着向左右两边扩展求最长的回文子串
                while (i+p[i]<newLen && i-p[i]>0&&s[i-p[i]]==s[i+p[i]]){
                    p[i]++;
                }
                //当前求出的回文字符串最右端的下标更大
                if(i+p[i]>id+p[id]){
                    id=i;
                }
                //当前求出的回文字符串更长
                if(p[i]-1>palindromeLen){
                    center=(i+1)/2-1;
                    palindromeLen=p[i]-1;//更新最长回文字符串的长度
                }
            }
        }

        public static void main(String[] args) {
            String str="abcbax";
            Manacher t=new Manacher();
            t.manacher(str);
            int center=t.getCenter();
            int palindromeLen=t.getLen();
            if(center!=-1 && palindromeLen!=-1){
                System.out.println("最长的回文字符串为：");
                //回文字符串长度为奇数
                if (palindromeLen % 2 == 1) {
                    for (int i=center-palindromeLen/2;i<=center+palindromeLen/2;i++){
                        System.out.print(str.charAt(i));
                    }
                }else {
                    for (int i=center-palindromeLen/2;i<=center+palindromeLen/2;i++){
                        System.out.print(str.charAt(i));
                    }
                }
            }else {
                System.out.println("查找失败");
            }
        }
    }
}
